package com.tucc.hello.leetcode.no1_400.no1_200.no149;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
        points = new int[][]{{84, 250}, {0, 0}, {0, -70}, {-42, -230}, {21, 10}, {42, 90}, {1, 0}, {1, -1}};
        System.out.println(solution.maxPoints(points));
    }

//    Map<String, Set<int[]>> ignoreMap = null;

    public int maxPoints(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt((int[] a) -> a[0]).thenComparingInt(a -> a[1]));
//        ignoreMap = new HashMap<>(points.length);
        int max = points.length >= 2 ? 2 : points.length;
        for (int i = 0; i < points.length - 2; i++) {
            for (int j = i + 1; j < points.length - 1; j++) {
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if (x != 0 && y != 0) {
                    int z = getGCD(x, y);
                    x = x / z;
                    y = y / z;
                }
                String key = x + "_" + y;
                if (x == 0) {
                    key = "0_";
                } else if (y == 0) {
                    key = "_0";
                }
//                Set<int[]> ignoreSet = ignoreMap.get(key);
//                if (ignoreSet != null) {
//                    if (ignoreSet.contains(points[i]) ||
//                            ignoreSet.contains(points[j]) ||
//                            ignoreSet.contains(points[j + 1])) {
//                        continue;
//                    }
//                } else {
//                    ignoreSet = new HashSet<>();
//                    ignoreMap.put(key, ignoreSet);
//                    ignoreSet.add(points[j]);
//                    ignoreSet.add(points[i]);
//                }
                int count = maxPoints(points, x, y, points[i][0], points[i][1], j + 1);//, ignoreSet);
                if (count > max) {
                    max = count;
                }
            }
        }
        return max;
    }

    public int maxPoints(int[][] points, int x, int y, int startX, int startY, int start) {//, Set<int[]> ignoreSet) {
        int count = 2;
        if (start < points.length) {
            for (int i = start; i < points.length; i++) {
                if (x == 0) {
                    if (points[i][0] == startX) {
//                        ignoreSet.add(points[i]);
                        count++;
                    } else {
                        break;
                    }
                } else if (y == 0) {
                    if (points[i][1] == startY) {
                        count++;
//                        ignoreSet.add(points[i]);
                    } else {
                        break;
                    }
                } else {
                    int d = points[i][0] - startX;
                    int nx = d / x;
                    if (nx * x == d) {
                        int exceptY = nx * y + startY;
                        if (points[i][1] == exceptY) {
                            count++;
//                            ignoreSet.add(points[i]);
                        }
                    }
                }
            }
        }
        return count;
    }

    public static int getGCD(int num1, int num2) {
        // 先获得绝对值，保证负数也可以求
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        // 假定第一个数较大；如果第二个较大，在第二轮会颠倒过来
        // 如果第二个数为 0，则第一个数就是最大公约数
        while (num2 != 0) {
            // 求余
            int remainder = num1 % num2;
            // 交换数，等同递归调用
            num1 = num2;
            num2 = remainder;
        }

        return num1;
    }
}
